package tests;


import linkcut.AuxVertex;
import linkcut.SplayTools;

import org.junit.Assert;
import org.junit.Test;


public class SplayTests {

	@Test
	public void oneVertex() {
		int value = 2;
		AuxVertex<Integer> v = new AuxVertex<Integer>(value);
		SplayTools.splay(v);
		Assert.assertTrue(v.isRoot());
		Assert.assertEquals(null, v.getLeft());
		Assert.assertEquals(null, v.getRight());
		Assert.assertSame(value, v.getValue());
	}
	
	/**
	 * An example from http://en.wikipedia.org/wiki/Splay_trees
	 */
	@Test
	public void simpleRightZig() {
		AuxVertex<Object> a = new AuxVertex<Object>();
		AuxVertex<Object> b = new AuxVertex<Object>();
		AuxVertex<Object> c = new AuxVertex<Object>();
		AuxVertex<Object> x = new AuxVertex<Object>(a, b);
		AuxVertex<Object> p = new AuxVertex<Object>(x, c);	
		SplayTools.splay(x);
		Assert.assertTrue(x.isRoot());
		Assert.assertEquals(a, x.getLeft());
		Assert.assertEquals(p, x.getRight());
		Assert.assertEquals(b, p.getLeft());
		Assert.assertEquals(c, p.getRight());
	}
	
	@Test
	public void simpleLeftZig() {
		AuxVertex<Object> c = new AuxVertex<Object>();
		AuxVertex<Object> l = new AuxVertex<Object>();
		AuxVertex<Object> r = new AuxVertex<Object>();
		AuxVertex<Object> x = new AuxVertex<Object>(l, r);
		AuxVertex<Object> p = new AuxVertex<Object>(c, x);	
		SplayTools.splay(x);
		Assert.assertTrue(x.isRoot());
		Assert.assertEquals(p, x.getLeft());
		Assert.assertEquals(r, x.getRight());
		Assert.assertEquals(c, p.getLeft());
		Assert.assertEquals(l, p.getRight());
	}
	
	/**
	 * An example from http://en.wikipedia.org/wiki/Splay_trees
	 */
	@Test
	public void simpleZigZig() {
		AuxVertex<Object> a = new AuxVertex<Object>();
		AuxVertex<Object> b = new AuxVertex<Object>();
		AuxVertex<Object> c = new AuxVertex<Object>();
		AuxVertex<Object> x = new AuxVertex<Object>(a, b);
		AuxVertex<Object> p = new AuxVertex<Object>(x, c);	
		AuxVertex<Object> d = new AuxVertex<Object>();
		AuxVertex<Object> g = new AuxVertex<Object>(p, d);
		SplayTools.splay(x);
		Assert.assertTrue(x.isRoot());
		Assert.assertEquals(a, x.getLeft());
		Assert.assertEquals(p, x.getRight());
		Assert.assertEquals(b, p.getLeft());
		Assert.assertEquals(g, p.getRight());
		Assert.assertEquals(c, g.getLeft());
		Assert.assertEquals(d, g.getRight());
	}
	
	/**
	 * An example from http://en.wikipedia.org/wiki/Splay_trees
	 */
	@Test
	public void simpleZigZag() {
		AuxVertex<Object> a = new AuxVertex<Object>();
		AuxVertex<Object> b = new AuxVertex<Object>();
		AuxVertex<Object> c = new AuxVertex<Object>();
		AuxVertex<Object> d = new AuxVertex<Object>();
		AuxVertex<Object> x = new AuxVertex<Object>(b, c);
		AuxVertex<Object> p = new AuxVertex<Object>(a, x);
		AuxVertex<Object> g = new AuxVertex<Object>(p, d);
		SplayTools.splay(x);
		Assert.assertTrue(x.isRoot());
		Assert.assertEquals(p, x.getLeft());
		Assert.assertEquals(g, x.getRight());
		Assert.assertEquals(a, p.getLeft());
		Assert.assertEquals(b, p.getRight());
		Assert.assertEquals(c, g.getLeft());
		Assert.assertEquals(d, g.getRight());
	}
	
	@Test
	public void ZigZagZig() {
		AuxVertex<Object> a = new AuxVertex<Object>();
		AuxVertex<Object> b = new AuxVertex<Object>();
		AuxVertex<Object> c = new AuxVertex<Object>();
		AuxVertex<Object> d = new AuxVertex<Object>();
		AuxVertex<Object> x = new AuxVertex<Object>(b, c);
		AuxVertex<Object> p = new AuxVertex<Object>(a, x);
		AuxVertex<Object> g = new AuxVertex<Object>(p, d);
		AuxVertex<Object> e = new AuxVertex<Object>();
		AuxVertex<Object> z = new AuxVertex<Object>(g, e);
		SplayTools.splay(x);
		Assert.assertTrue(x.isRoot());
		Assert.assertEquals(p, x.getLeft());
		Assert.assertEquals(z, x.getRight());
		Assert.assertEquals(a, p.getLeft());
		Assert.assertEquals(b, p.getRight());
		Assert.assertEquals(c, g.getLeft());
		Assert.assertEquals(d, g.getRight());
		Assert.assertEquals(g, z.getLeft());
		Assert.assertEquals(e, z.getRight());
	}

}
